/*
 * 0081. Find Median from Data Stream
 * 数字是不断进入数组的，在每次添加一个新的数进入数组的同时返回当前新数组的中位数。
 * https://www.lintcode.com/problem/find-median-from-data-stream/description
 * 
 * 样例
 * 持续进入数组的数的列表为：[1, 2, 3, 4, 5]，则返回[1, 1, 2, 2, 3]
 * 持续进入数组的数的列表为：[4, 5, 1, 3, 2, 6, 0]，则返回 [4, 4, 4, 3, 3, 3, 3]
 * 持续进入数组的数的列表为：[2, 20, 100]，则返回[2, 2, 20]
 * 
 * 挑战
 * 时间复杂度为O(nlogn)
 * 
 * 2018.06.30 @jeyming
 */
package find_median_from_data_stream_0081;

import java.util.Arrays;

public class Find_median_from_data_stream_0081 {
    /**
     * @param nums: A list of integers
     * @return: the median of numbers
     */
    public int[] medianII(int[] nums) {
        // write your code here
    	int[] median = new int[nums.length];
    	for(int i = 0; i < nums.length; ++i) {
        	Arrays.sort(nums, 0, i + 1);
    		median[i] = nums[i / 2];
    	}
    	return median;
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
